1207. Корень, логарифм, синус
Злой профессор
только что задал Вам следующую задачу. Определим последовательность следующим
образом:
x0 = 1,
xi = 
+ 
+ 
Для каждого значения i вычислите xi.
Вход. Состоит из нескольких строк, каждая из которых содержит
одно целое число i (0 ≤ i ≤ 106). Последняя строка содержит -1 и не
обрабатывается.
Выход. Для каждого
значения i (кроме последнего -1) выведите
соответствующее значение xi, вычисленное по модулю 106.
|
Пример
входа |
Пример
выхода |
|
0 1 2 10 -1 |
1 3 5 21 |
РЕШЕНИЕ
рекуррентное
соотношение
Анализ алгоритма
Значение xi будем вычислять при помощи
функции f(i). Для этого следует реализовать
рекуррентность
= 
+ 
+ 
,
с запоминанием значений f(i) в линейном массиве dp размером 106.
Реализация алгоритма
Значения xi будем хранить в массиве dp.
#define MAX 1000001
int dp[MAX];
Функция f(n) вычисляет значение xn.
int f(int n)
{
Условие окончания рекурсии.
if (n ==
0) return 1;
Если значение xn уже вычислено (dp[n] ≠ -1),
возвращаем его.
if (dp[n] != -1) return dp[n];
Вычисляем рекурсивно первое, второе и
третье слагаемое.
int a = f((int)(n
- sqrt(n)));
int b = f((int)(log(n)));
int c = f((int)(n * sin(n) * sin(n)));
Вычисляем, запоминаем и возвращаем
значение xn.
return dp[n] = (a + b +
c) % 1000000;
}
Основная часть программы. Пусть dp[i] = -1, если значение xi еще не вычислено.
memset(dp,-1,sizeof(dp));
Обрабатываем несколько тестов. Для каждого значения n выводим ответ.
while(scanf("%d",&n),
n != -1)
printf("%d\n",f(n));
Реализация алгоритма – не рекурсивная
Значения xi будем хранить в массиве x.
int x[1000001];
Заполняем элементы массива x согласно заданной рекуррентности.
x[0] = 1;
for (i = 1; i <= 1000000; i++)
x[i]
= (x[(int)(i - sqrt(i))] + x[(int)(log(i))]
+
x[(int)(i *
sin(i) * sin(i))]) % 1000000;
Обрабатываем несколько тестов. Для каждого значения n выводим ответ.
while (scanf("%d",
&n), n != -1)
printf("%d\n",
x[n]);
Java реализация
import java.util.*;
public class Main
{
static int dp[] = new int[1000001];
static int f(int n)
{
if (n ==
0) return 1;
if (dp[n] !=
-1) return dp[n];
int a = f((int)(n -
Math.sqrt(n)));
int b = f((int)(Math.log(n)));
int c = f((int)(n *
Math.sin(n) * Math.sin(n)));
return dp[n] = (a + b + c) %
1000000;
}
public static void
main(String[] args)
{
Scanner con = new
Scanner(System.in);
Arrays.fill(dp,
-1);
while(true)
{
int n = con.nextInt();
if (n ==
-1) break;
System.out.println(f(n));
}
con.close();
}
}
Python реализация
import math
Инициализируем массив x.
x = [0] * 1000001
x[0] = 1
Заполняем элементы массива x согласно заданной рекуррентности.
for i in range(1, 1000001):
x[i] = (x[int(i - math.sqrt(i))] +
x[int(math.log(i))] +
x[int(i * math.sin(i)**2)]) % 1000000
Обрабатываем несколько тестов. Для каждого значения n выводим ответ.
while True:
n = int(input())
if n == -1:
break
print(x[n])